package part1.three;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @Author: shaochong
 * @Date: 2021/8/6
 * @Description:
 */
public class SolutionThree {
    public int lengthOfLongestSubstring(String s) {
        int len = s.length();
        int left = 0;
        int right = 0;
        int ans = 0;

        // 用于记录滑动窗口内出现的字符
        Set set = new HashSet<Character>();

        // 外层循环,窗口起点<len
        while (left < len) {

            // 内层循环,依次扩大右边界;终止条件是该字符在滑动窗口内已经出现,说明有重复
            while (right < len && !set.contains(s.charAt(right))) {
                set.add(s.charAt(right));
                right++;
            }
            // 记录本滑动窗口的长度,为其中的一个解,使用ans记录最大解
            ans = Math.max(ans, right - left);

            // 左侧窗口收缩
            set.remove(s.charAt(left));
            left++;
        }
        return ans;
    }


    /**
     * 改进,左侧收缩时直接跳跃到不包含字符的位置
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring2(String s) {
        int len = s.length();
        int left = 0;
        int right = 0;
        int ans = 0;

        Map<Character, Integer> map = new HashMap<Character, Integer>();

        // 外层循环,窗口起点<len
        while (left < len) {

            int position = 0;
            // 内层循环,依次扩大右边界;终止条件是该字符在滑动窗口内已经出现,说明有重复
            while (right < len && !map.containsKey(s.charAt(right))) {
                map.put(s.charAt(right), right);
                right++;
            }

            // 记录本滑动窗口的长度,为其中的一个解,使用ans记录最大解
            ans = Math.max(ans, right - left);

            if (right < len) {
                position = map.get(s.charAt(right));
                // 左侧窗口直接收缩多个位置
                for (int i = left; left<position; i++) {
                    map.remove(s.charAt(i));
                }
                left = position;
            }
            left++;
        }
        return ans;
    }


}
